#include "NodesHashtable.h"

NodesHashtable::NodesHashtable(int maxCapacity)
{
	bucket=new int[maxCapacity];
	nodes=new SearchNode[maxCapacity];
	this->maxCapacity=maxCapacity;
	stored=0;
	empty=0;


	// Clear the hashtable
	for (int index = 0; index < maxCapacity; index++)                    /* empty hash table */
	{
		nodes[index].g = -1;                  /* only g value checked for emptiness */
		nodes[index].link = maxCapacity;
		nodes[index].h = -1;
		nodes[index].cost=-1;
		bucket[index] = maxCapacity;           /* initialize hash table buckets to empty */
	}
}

NodesHashtable::~NodesHashtable(void)
{
	delete[] bucket;
	delete[] nodes;
}


/* SEARCH takes a packed state and its hash value, and returns the index in the
hash table where it is located. Collisions are handled by searching down the
linked chain of the bucket. If the state is not in the table, it returns -1. 
Parameters:
int ps[WORDS];                                  packed state of puzzle 
int hashval;                                   the hash value of the state 
*/
int NodesHashtable::search(unsigned int ps[WORDS],int hashval)
{
	int index;                        /* index to different states in hash table */
	int pos;                            /* index to different positions in state */

	index = bucket[hashval];                     /* first state in target bucket */

	while (index != maxCapacity)                         /* end of chain not reached yet */
	{
		// DEBUG
		assert((index>=0) && (index<maxCapacity));
		// END DEBUG
		for (pos = 0; pos < WORDS; pos++)           /* each position in the state */
			if (ps[pos] != nodes[index].ps[pos])
				break;							    /* mismatch: exit for loop */
		if (pos == WORDS)
			return (index);					/* state found, return location */
		else
			index = nodes[index].link;                   /* next state on chain */
	}

	return (-1);                        /* state not found, return failure flag */
}

/**
 * A slower implementation of search, used for DEBUG 
 **/
int NodesHashtable::search (unsigned int ps0, unsigned int ps1)
{
	unsigned int ps[2];
	ps[0]=ps0;
	ps[1]=ps1;
	int hashvalue = hash(ps);
	return search(ps,hashvalue);
}


/* INSERT takes a packed state, its hash value, its previous blank position, its
g value, and its static h value, and inserts it in the OPEN list in sorted order
using g and h. Returns the index of the inserted node.
Parameters:
int ps[WORDS];                              packed state 
int hashval;                                the hash value of the state 
int oldblank;                               previous position of blank 
int g;                                      distance from initial state 
int h;                                      static heuristic value of state 
*/
int NodesHashtable::insert(unsigned int ps[WORDS],int hashval,int oldblank,int g,int h, int cost,int parentIndex)
{
	int word;                                            /* word in packed state */
	int index;                           /* index in hash table where state goes */

	index = empty++;           /* store in first empty location and bump pointer */
	// DEBUG
	assert(index<maxCapacity);
	// END DEBUG
	stored++;                        /* increment number of states in hash table */
	
	for (word = 0; word < WORDS; word++)        /* for each word of packed state */
		nodes[index].ps[word] = ps[word];       /*  store first word of packed state */

	nodes[index].link = bucket[hashval];      /* next pointer to old first element */
	bucket[hashval] = index;               /* new state is at head of hash chain */

	nodes[index].oldblank = oldblank;                /* previous position of blank */
	nodes[index].h = h;                               /* store new heuristic value */
	nodes[index].g = g;                               /* store distance from start */
	nodes[index].cost = cost;
	nodes[index].heapIndex=-1;
	nodes[index].parent = parentIndex;

	return index;
}

/** This function checks if the number of stored nodes exceeds the maximum capacity */
bool NodesHashtable::isFull()
{
	return stored>=maxCapacity;
}





/* HASH takes a packed state and returns an integer (possibly negative) which
is its target bucket in the hash table. 
ps - packed state of puzzle */
long NodesHashtable::hash(unsigned int ps[WORDS])                                      
{
	int index;                                              /* tile being hashed */
	long long int value;                                                     /* hash value */

	value = ps[0];                                             /* starting value */
	for (index = 1; index < WORDS; index++)          /* for each additional tile */
		value = value * 3 + ps[index];                   /* add new tile in base 3 */

	value = (value>=0? value : -value);  /* Implementation of ABS(int) to support long long int */

	return(value % MAX);						  /* returned value will be mod 2 ^ word size */
}
